package com.yun.algorithmproblem.leetcode;

public class Leetcode53 {

    /**
     *自己想的方法，时间复杂度O(n)
     * @param nums 需要处理的数组
     * @return  和最大的连续子数组的值
     */
    public int maxSubArray1(int[] nums) {
        int current=0;
        int max=nums[0];
        for (int i = 1; i < nums.length; i++) {
            current=current+nums[i];
            if(max<current){
                max=current;
            }
            if (current<0){
                current=0;
            }
        }
        return max;
    }

    /**
     * 动态规划
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int pre=0;
        int res=nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(pre, res);
        }
        return res;
    }

    /**
     * 递归
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        return getInfo(nums,0,nums.length-1).mSum;
    }

    public static class Status{
        int lSum,rSum,mSum,iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public Status getInfo(int[] nums,int l,int r){
        if(l==r){
            return new Status(nums[l], nums[l], nums[l], nums[l]);
        }
        int m=(l+r)>>>2;
        Status lSub=getInfo(nums,l,m);
        Status rSub=getInfo(nums,m+1,r);
        return pushUp(lSub,rSub);
    }

    public Status pushUp(Status l,Status r){
        int lSum=Math.max(l.lSum,l.iSum+r.lSum);
        int rSum=Math.max(r.rSum,r.iSum+l.rSum);
        int mSum=Math.max(Math.max(l.mSum,r.mSum),l.rSum+r.lSum);
        int iSum=l.iSum+r.lSum;
        return new Status(lSum, rSum, mSum, iSum);
    }

}
